package model;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tymoshya
 * @since 20.08.12
 */
public class QueenPlacer {

    public static final int N = 8;

    private static boolean solved;
    static List<Cell> queensPlaced;

    public static void place() {
        solved = false;
        queensPlaced = new ArrayList<Cell>();
        queensPlaced.add(Cell.random(N, N));
        backtrack(queensPlaced, 0);
    }

    public static List<Cell> place2() {
        place();
        return new ArrayList<Cell>(queensPlaced);
    }

    /**
     *
     * @param placedQueens - vector[1..N] which will contain placed queens
     * @param k - a position of the last queen, placed in the vector "placedQueens" (0 <= k < N)
     */
    static void backtrack(List<Cell> placedQueens, int k) {
        List<Cell> a = new ArrayList<Cell>(placedQueens);
        if (isASolution(a)) {
            solved = true;
            processSolution(a);
        } else if(!solved) {
            k++;
            List<Cell> candidates = constructCandidates(a);
            for (Cell candidate : candidates) {
                if(a.size() <= k) {
                    a.add(candidate);
                } else {
                    a.set(k, candidate);
                }
                backtrack(a, k);
            }
        }
    }

    private static List<Cell> constructCandidates(List<Cell> queensPlaced) {
        List<Cell> result = new ArrayList<Cell>();
        Cell currentCell;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                currentCell = new Cell(i, j);
                if (!queensPlaced.contains(currentCell) && !isUnderAttack(currentCell, queensPlaced)) {
                    result.add(currentCell);
                }
            }
        }
        return result;
    }

    private static boolean isASolution(List<Cell> queensPlaced) {
        return queensPlaced.size() == N;
    }

    private static boolean isUnderAttack(Cell currentQueen, List<Cell> queensPlaced) {
        boolean result = false;
        List<Cell> otherQueens = new ArrayList<Cell>(queensPlaced);
        if (otherQueens.contains(currentQueen)) {
            otherQueens.remove(currentQueen);
        }
        for (Cell cell : otherQueens) {
            if ((currentQueen.getI() == cell.getI()) || (currentQueen.getJ() == cell.getJ()) || Cell.onTheSameDiagonal(currentQueen, cell)) {
                result = true;
                break;
            }
        }
        return result;
    }

    private static void processSolution(List<Cell> a) {
        queensPlaced = a;
    }
}